//: [Previous](@previous)

import Foundation

/*:
 ### Remove Nth Node From End of List
 LeetCode上第19号问题：删除链表的倒数第N个节点
 ```
 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 示例：
 
 给定一个链表: 1->2->3->4->5, 和 n = 2.
 当删除了倒数第二个节点后，链表变为 1->2->3->5
 说明：
 
 给定的 n 保证是有效的。
 进阶：
 
 你能尝试使用一趟扫描实现吗？
 ```
 */

var list = SinglyLinkedList(arr: [1,2,3,4,5])

func Solution(_ head: ListNode?, _ n: Int) -> ListNode? {
    guard let head = head else {
        return nil
    }
    
    let dummayHead = ListNode(0)
    dummayHead.next = head
    var p = dummayHead
    var q: ListNode? = dummayHead
    
    for _ in 0...n {
        q = q?.next
    }
    
    while q != nil {
        p = p.next!
        q = q?.next
    }
    
    p.next = p.next?.next
    
    return dummayHead.next
}

list.head = Solution(list.head, 2)
print(list)

//: [Next](@next)
